class UnionFind2:
    """
    数组的下标表示元素
    数组self.parent下标对应的值为元素对应的父节点
    如果父节点和元素一样那么该元素为单独的一个组
    """
    def __init__(self, n):
        self.count = n 
        self.parent = [0]*n
        # 初始：每个元素互不连接
        for i in range(n):
            self.parent[i] = i
    
    # 找到p对应的根节点
    def find(self, p):
        assert p >= 0 and p < self.count
        while p != self.parent[p]:
            p = self.parent[p]
        return p
    
    # 有相同的根
    def is_connected(self, p, q):
        return self.find(p) == self.find(q)

    def union(self, p, q):
        p_root = self.find(p)
        q_root = self.find(q)

        # 已经相连，什么也不做
        if p_root == q_root:
            return
        
        self.parent[p_root] = q_root
